#include <stdio.h>

#include <iostream>
using namespace std;

template <class T>

int getLength(T &array)
{
    return sizeof(array) / sizeof(array[0]);
}

void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
    {
        cout << array[i] << " ,";
    }
    cout << endl;
}

void copyArray(int nums[], int array[], int length)
{
    for (int i = 0; i < length; i++)
    {
        array[i] = nums[i];
    }
}

void swap(int nums[], int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

/*******************************插入排序*******************************/
/**
 * 直接插入排序
 * 假设a[0]作为哨兵元素，不包含于L序列
 * 1)查找出L[i]在已有序的子序列L[1,2,...,i-1]中插入的位置k
 * 2)将L[k,...,i-1]元素依次后移一个位置
 * 3)将L[i]赋值到L[k]
 *  */
void insertSort(int a[], int n)
{
    int i, j;
    for (i = 1; i <= n; i++)
    {
        if (a[i] < a[i - 1])
        {
            a[0] = a[i];
            for (j = i - 1; a[0] < a[j]; j--)
                a[j + 1] = a[j];
            a[j + 1] = a[0];
        }
    }
}

/**
 *希尔排序：
 * 思路：本质是直接插入排序,
 * 测试用例：{49 ,38, 65, 97, 76, 13, 27, 49, 55, 4}
 * 背景：当序列基本有序的时候直接插入排序效率相对较高
 * 思想：先追求序列中的元素部分有序，然后追求全局有序。
 *          1.将元素分割成若干形如L[i,i+d,i+2d,...,i+kd]的特殊子表，对各个子表分别进行直接插入排序。
 *          2.然后缩小增量d，重复上述过程，直到d=1为止。
 */
void xierSort(int nums[], int length, int gap)
{
    // 经典希尔算法的gap值为 length/2，length/4
    for (; gap >= 1; gap /= 2)
    {
        // 使用直接插入排序
        for (int i = gap; i < length; i += gap)
        {
            int temp = i;
            for (int j = i - gap; j >= 0; j -= gap)
            {
                if (nums[temp] > nums[j])
                    break;
                else
                {
                    nums[temp] = nums[j] + nums[temp];
                    nums[j] = nums[temp] - nums[j];
                    nums[temp] = nums[temp] - nums[j];
                }
                temp -= gap;
            }
        }
    }
}

/*
 *折半插入排序 (nums原始数组已排序完成，num：待插入数据，length，数组长度)
 *思路：先二分查找到该插入的位置，然后插入
 */
void binarySort(int nums[], int length, int key)
{
    // 1二分查找到目标位置
    int low = 0, high = length - 2;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        cout << "low:" << low << "high:" << high << "mid" << mid;
        if (nums[mid] >= key && nums[mid - 1] <= key)
        {
            // 找到对应位置，开始执行插入
            for (int i = length - 1; i > mid; i--)
            {
                nums[i] = nums[i - 1];
            }
            nums[mid] = key;
            break;
        }
        else if (nums[mid] < key)
        {
            low = mid + 1;
        }
        else if (nums[mid] > key)
        {
            high = mid - 1;
        }
    }
}

/*******************************交换排序*******************************/
/**
 * 冒泡排序：测试用例：{49 ,38, 65, 97, 76, 13, 27, 49, 55, 4};
 * 思路：两层循环，大数向后移动，小数向前移动
 * */
void bubbleSort(int nums[], int length)
{
    for (int i = 0; i < length; i++)
    {
        int temp = i;
        for (int j = temp + 1; j < length; j++)
        {
            if (nums[j] < nums[temp])
            {
                nums[temp] = nums[j] + nums[temp];
                nums[j] = nums[temp] - nums[j];
                nums[temp] = nums[temp] - nums[j];
            }
        }
    }
}

/**
 * 快速排序：测试用例：{49 ,38, 65, 97, 76, 13, 27, 49, 55, 4};
 * 思路：递归，取一个数组nums的第一个元素a，将该数组的所有元素大于a的放到数组后面，小于a的放到前面
 * 如此不断循环
 * */
void quickSort(int nums[], int low, int high)
{
    if (low < high)
    {
        int pivotpos = partition(nums, low, high);
        quickSort(nums, low, i - 1);
        quickSort(nums, i + 1, high);
    }
}
int Partition(int nums[], int low, int high)
{
    int pivot = nums[low]; // 定义一个哨兵元素
    while (low < high)
    {
        while (low < high && pivot <= nums[high])
            high--;
        nums[low] = nums[high]; // 将比枢轴小的元素移到左边

        while (low < high && pivot >= nums[low])
            low++;
        nums[high] = nums[low]; // 将比枢轴大的元素移动到右边
    }
    nums[low] = pivot; // 枢轴元素存放的最终位置
    return low;        // 返回存放枢轴的最终位置
}

// quickSort:
// if(low < high){
//         int i = low, j = high, temp = nums[low];//定义数组第一元素为哨兵元素
//         while (i < j)//循环将数组中大于哨兵的元素放到后面去，将小于哨兵的元素放到前面去
//         {
//             while (i < j && nums[j] >= temp)j--;
//             //找到一个大于temp，但处于前面的元素，需要将其放到后面去
//             if (i < j)
//             {
//                 nums[i] = nums[j];
//                 // swap(nums,i,j);
//                 i++;
//             }
//
//             while (i < j && nums[i] <= temp)i++;
//             //找到一个大于temp，但处于前面的元素，需要将其放到后面去
//             if (i < j)
//             {
//                 // swap(nums,i,j);
//                 nums[j] = nums[i];
//                 j--;
//             }
//             nums[i] = temp;
//         }
//         quickSort(nums,low,i-1);
//         quickSort(nums,i+1,high);
//     }

/**
 * 王道8.3.3.5
 * 6.试编写一个算法，使之能够在数组L[1...n]中找到第k小的元素(即从小到大排序后处于第k个位置的元素)。王道P328
 * 快速排序思想
 * ①从数组L中选择第一个元素作为pivot，进行和快速排序一样的划分操作，设下标为i。
 * 此时数组被分割成L[1,...,i-1]，L[i]，L[i+1,...,n]
 * ②当i =k时，pivot就是要找的元素
 * ③当i < k时，第k小的元素在L[i+1,...,n]中，递归查找L[i+1,...,n]即可
 * ④当i>k时，第k小的元素在L[1,...,i-1]中，递归查找L[1,...,i-1]即可
 */
int kthElem(int a[], int low, int high, int k)
{
    int pivot = a[low];
    int low_temp = low; // 由于下面会修改low与high,在递归时又要用到它们
    int high_temp = high;
    while (low < high)
    {
        while (low < high && a[high] >= pivot)
            --high;
        a[low] = a[high];
        while (low < high && a[low] <= pivot)
            ++low;
        a[high] = a[low];
    }
    a[low] = pivot;
    // 上面即为快速排序中的划分算法
    // 以下就是本算法思想中所述的内容
    if (low == k) // 由于与k相同，直接返回pivot 元素
        return a[low];
    else if (low > k) // 在前一部分表中递归寻找
        return kthElem(a, low_temp, low - l, k);
    else // 在后一部分表中递归寻找
        return kthElem(a, low + 1, high_temp, k);
}

/*******************************选择排序*******************************/
/**
 * 简单选择排序：每次从待排序序列中选择一个最小值交换到待排序序列的起始位置
 * 思路：扫描待排序序列，从中找出最小的元素加入到已排序的序列中
 * */
void simpleSelectSort(int nums[], int length)
{
    for (int i = 0; i < length; i++)
    {
        int temp = i;
        // 进行一次循环找出数组中最小的元素
        for (int j = i; j < length; j++)
        {
            if (nums[j] < nums[temp])
            {
                temp = j;
            }
        }
        int a = nums[temp], b = nums[i];
        swap(nums, temp, i);
        printArray(nums, length);
    }
}

/**
 * 堆排序：要求：1.完全二叉树，2.根节点大于两个孩子结点
 * 调整的时间与树高有关，为0(h)。
 * 在建含n个元素的堆时，关键字的比较总次数不超过4n,时间复杂度为 0(n)
 * 这说明可以在线性时间内将一个无序数组建成一个堆。
 * */
void BuildMaxHeap(int A[], int len)
{
    for (int i = len / 2; i > 0; i--) // 从i=[n/2]~1,反复调整堆
        HeadAdjust(A, i, len);
}
// 函数 headAdjust 将元素k为根的子树进行调整
void HeadAdjust(int A[], int k, int len)
{                
    A[0] = A[k];                            // A[0]暂存子树的根结点
    for (int i = 2 * k; i <= len; i *= 2)   
    {                                       //不断让小元素下沉，并沿key较大的子结点向下筛选
        if (i < len && A[i] < A[i + 1])     //比较两个孩子哪个结点比较大，取key较大的子结点的下标
            i++;
        if (A[0] >= A[i])                   //判断当前结点是否比更大的孩子还要大
            break;                          
        else
        {
            A[k] = A[i];                    // 将A[i]调整到双亲结点上
            k = i;                          // 修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0];                            // 被筛选结点的值放入最终位置
}
/**
 * 下面是堆排序算法:
 *      每一次将堆顶元素加入有序子序列
 *      即，与待排序序列中最后一个元素交换并设置堆数组为nums[1:n-1]，有序数组为nums[n]
 *      然后将换到堆顶的元素不断下坠。
 *      如此不断重复，直到堆数组长度为1
 */ 
void HeapSort(int A[], int len)
{
    BuildMaxHeap(A, len);        // 初始建堆
    for (int i = len; i > l; i--)
    {                            // n-1 趟的交换和建堆过程
        Swap(A[i], A[1]);        // 输出堆顶元素(和堆底元素交换)
        HeadAdjust(A, 1, i - 1); // 调整，把剩余的i-1个元素整理成堆
    }
}
// void heapify(int tree[], int length, int i)
// { // i表示第i个结点
//     // 经过顺序调换，使该元素的根结点为最大值
//     if (i < length)
//     {
//         // i结点的左右孩子结点下标lChild，rChild
//         int lChild = 2 * i + 1;
//         int rChild = 2 * i + 2;
//         int max = i;
//         if (lChild < length && tree[max] < tree[lChild])
//         {
//             max = lChild;
//         }

//         if (rChild < length && tree[max] < tree[rChild])
//         {
//             max = rChild;
//         }
//         if (max != i)
//         {
//             swap(tree, max, i);
//             // 交换后，确保其子树也满足要求
//             heapify(tree, length, max);
//         }
//     }
// }
// void buildHeap(int tree[], int length)
// {
//     int last = length - 1; // 最后一个结点
//     int parent = (last - 1) / 2;
//     for (int i = parent; i >= 0; i--)
//     {
//         heapify(tree, length, i);
//     }
// }
// void heapSort(int tree[], int length)
// {
//     buildHeap(tree, length);
//     for (int i = length - 1; i >= 0; i--)
//     {
//         swap(tree, i, 0);
//         heapify(tree, i, 0);
//     }
// }

/**
 * 归并排序：测试用例：{49 ,38, 65, 97, 76, 13, 27, 49, 55, 4};
 * 思路：将数组一般对一般分开，然后合并
 * 时间复杂度 = 将数组分开的O(logn) * 将排列好的数据赋给原数据O(n)
 * */
/**
 * 思路:    1.定义一个空数组temp[]，长度与待合并数组一致，用于存放合并时的数据
 *          2.定义双指针i,j，分别从两段数据的开头（low,mid+1），开始比较，将较小的一个放入temp，直到遍历完一组数据
 *          3.将剩下的直接全部放入temp中
 *          4.将temp里的数据赋给原数组
 * */
// 合并两个有序的子数组
void merge(int nums[], int low, int mid, int high)
{
    if (low < high)
    {
        int i = low, j = mid + 1, k = 0;
        int *temp = (int *)malloc((high - low + 1) * sizeof(int));

        while (i <= mid && j <= high)
        {
            temp[k++] = (nums[i] <= nums[j]) ? nums[i++] : nums[j++];
        }
        // 复制剩余元素
        while (i <= mid)
        {
            temp[k++] = nums[i++];
        }
        while (j <= high)
        {
            temp[k++] = nums[j++];
        }
        // 将归并好的数据赋给nums[]
        for (k = 0, i = low; i <= high; k++, i++)
        {
            nums[i] = temp[k];
        }
        free(temp);
    }
}
void mergeSort(int nums[], int low, int high)
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        mergeSort(nums, low, mid);
        mergeSort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }
}

int main()
{
    // 直接插入排序
    //  int nums[] = {8,2,4,7,6,9,5,1};
    //  int length = getLength(nums);
    //  insertSort(nums,length);
    //  cout<<"直接插入排序:";
    //  printArray(nums,length);

    // 折半插入排序
    //  int key = 3;
    //  int array[length+1];
    //  copyArray(nums,array,length);
    //  binarySort(array,length+1,key);
    //  cout<<"折半插入排序:";
    //  printArray(array,length+1);

    int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    int length = getLength(array);
    // 希尔排序
    //  xierSort(array, length, 1);

    // 冒泡排序
    //  bubbleSort(array,length);

    // 快速排序
    //  cout<<"快速排序前：";
    //  printArray(array,length);
    //  quickSort(array,0,length-1);
    //  cout<<"快速排序后：";
    //  printArray(array,length);

    // 简单选择排序
    //  cout<<"简单选择排序：";
    //  printArray(array,length);
    //  simpleSelectSort(array,length);
    //  cout<<"简单选择排序：";
    //  printArray(array,length);

    // 堆排序
    //  cout<<"堆排序排序前：";
    //  printArray(array,length);
    //  heapSort(array,length);
    //  cout<<"堆排序排序后：";
    //  printArray(array,length);

    // 归并排序
    cout << "归并排序排序前：";
    printArray(array, length);
    mergeSort(array, 0, length - 1);
    cout << "归并排序排序后：";
    printArray(array, length);

    return 0;
}